The present invention generally relates to methods and apparatus for digital signal processing or computational operations.
It is sometimes desired to find the greatest of a set of values that may be electrically stored as a set of digital words in memory elements such as registers, random access memory ("RAM") or read-only memory ("ROM"). Also, it is often desired to identify the largest such value, e.g., by finding its associated index number, which may be the number of the memory element in which the largest value is stored.
A common method for finding the largest of a set of values involves sequentially scanning the set. A register for storing the largest value is loaded with the first value (and its index), and the contents of the register is compared to the second value. If the second value is larger, the second value and its index replace the first value and its index in the register. The third value is then compared to the register contents, and if it is larger, the third value and its index replace the value and index stored in the register. The process continues until all subsequent values in the set have been compared to the register contents.
Unfortunately, the amount of time needed for such a sequential search is proportional to the number of values in the set; thus, a sequential search may be too slow when the set is large. As described in more detail below, the present invention provides a fully parallel search method and circuit implementation using bit-serially presented digital values that determine the maximum value and its index in a time period that is independent of the number of values in the set searched.
The present invention is particularly useful for code division multiple access ("CDMA") communications techniques in cellular radio telephone communication systems, such as the enhanced CDMA demodulation scheme based on successive signal subtractions, in signal strength order, of multiple CDMA signals that is described in co-pending U.S. Patent application Ser. No. 07/628,359, filed Dec. 17, 1990;
In that co-pending patent application, it is explained that superior methods of spectrally spreading an information signal, such as occurs in a CDMA system, use error correction coding. When a single information bit is expanded into a pseudo-random sequence of R bits, the information bandwidth is spread without error-correction-coding gain; this technique may be termed "simple spreading". On the other hand, spreading a block of M information bits, where M&gt;1, into a pseudo-random sequence of M.times.R bits provides an error correction coding gain of the spreading ratio R. This technique, called "intelligent spreading", can involve either orthogonal or bi-orthogonal block coding of the information signal to be transmitted.
In orthogonal block coding, M bits to be transmitted are converted to one of 2.sup.M available 2.sup.M -bit orthogonal codewords. Decoding involves correlating a received signal with all members of the set of orthogonal codewords, and the index of the codeword giving the highest correlation yields the desired information. For example, if a signal's correlation with sixteen 16-bit codewords index-numbered 0 to 15 produces the highest correlation on the tenth codeword, the desired signal information is the 4-bit binary word 1010 (decimal 10).
A comparison processor may determine which correlation has the largest magnitude and may set that signal to zero by opening a corresponding switch. In this manner, the demodulated signal is subtracted effectively from the composite signal. The remaining spectrum with one component removed is processed and re-scrambled to reconstruct the original signal samples less the just-decoded signal. The magnitude of the correlated signal is representative of signal strength and may be stored in a sorting processor along with the signal's corresponding scrambling code. The processor orders the scrambling codes from greatest to weakest correlated signal magnitudes, and the code corresponding to the greatest magnitude may then be transmitted to the descrambler for the next signal demodulation.
Thus, after the comparison processor detects real and imaginary correlations and determines complex correlation magnitudes by calculating the square root of the sum of the squares of the real and imaginary components, the processor may then determine which complex correlation has the greatest magnitude. The real and imaginary components of the selected correlation may also be analyzed in the complex plane to determine if the phase has changed.